import java.util.Locale;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-08-26
 * Time: 22:52
 */
public class Solution2 {
    public String LCS (String s1, String s2) {
        //构造最长公共子序列的长度数组，然后通过数组去还原字符串，找到公共的字符进行拼接
        int n=s1.length();
        int m=s2.length();
        int[][] dp=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        //找出了最长公共子序列的长度，然后进行还原
        if(dp[n][m]==0){
            return "-1";
        }
        //从后面还原
        //使用字符串拼接
        StringBuilder tmp=new StringBuilder();
        //n==0 / m==0是空串
        while (n>0 & m>0){
            if(s1.charAt(n-1)==s2.charAt(m-1)){
                //两个位置字符相同，那么继续往前拼接
                tmp.append(s1.charAt(n-1));
                n--;
                m--;
            }else if(dp[n][m-1]>dp[n-1][m]){
                //由左边的变化而来
                m--;
            }else{
                n--;
            }
        }
        return tmp.reverse().toString();
    }
}
